home *** CD-ROM | disk | FTP | other *** search
/ Technotools / Technotools (Chestnut CD-ROM)(1993).ISO / lang_c / cug172 / lex.c < prev    next >
C/C++ Source or Header  |  1986-02-05  |  19KB  |  647 lines
  1. /*
  2.   HEADER: CUG     nnn.nn;
  3.   TITLE:     LEX - A Lexical Analyser Generator
  4.   VERSION:     1.0 for IBM-PC
  5.   DATE:      Jan 30, 1985
  6.   DESCRIPTION:     A Lexical Analyser Generator. From UNIX
  7.   KEYWORDS:     Lexical Analyser Generator YACC C PREP
  8.   SYSTEM:     IBM-PC and Compatiables
  9.   FILENAME:      LEX.C
  10.   WARNINGS:     This program is not for the casual user. It will
  11.          be useful primarily to expert developers.
  12.   CRC:         N/A
  13.   SEE-ALSO:     YACC and PREP
  14.   AUTHORS:     Scott Guthery 11100 leafwood lane Austin, TX 78750
  15.   COMPILERS:     DESMET-C
  16.   REFERENCES:     UNIX Systems Manuals
  17. */
  18. /*
  19.  * Copyright (c) 1978 Charles H. Forsyth
  20.  */
  21.  
  22. /*
  23.  * lex -- initialisation, allocation, set creation
  24.  *
  25.  *     Revised for PDP-11 (Decus) C by Martin Minow
  26.  */
  27.  
  28. /* Modified 02-Dec-80 Bob Denny -- Conditionalized debug code for smaller size
  29.  *                           01 -- Moved calls to dfa build, min, print, write
  30.  *                                  and to stat, and code for ending() into
  31.  *                                  this module so that 'ytab' could be put
  32.  *                                  into overlay region.
  33.  *          29-May-81 Bob Denny -- More extern hacking for RSX overlaying.
  34.  * More     19-Mar-82 Bob Denny -- New C library & compiler
  35.  * More     03-May-82 Bob Denny -- Final touches, remove unreferenced autos
  36.  *          28-Aug-82 Bob Denny -- Add "-s" switch to supress references to
  37.  *                                  "stdio.h" in generated code.  Add switch
  38.  *                                  comments in code. Add -e for "easy" com-
  39.  *                                  mand line. "lex -e file" is the short way
  40.  *                                  of saying:
  41.  *                                      "lex -i file.lxi -o file.c -t file"
  42.  * More(!)  30-Oct-82 Bob Denny -- Fix RSX ODL to put lots of FCS junk into
  43.  *                                  overlay, pick up (badly needed) 3KW for
  44.  *                                  NFA nodes, etc.  Change static allocations
  45.  *                                  in LEXLEX.H for RSX so can do non-trivial
  46.  *                                  things.  Task is now big on RSX and grows
  47.  *                                  from big to huge as it runs.
  48.  *                                 Fix "-s" support so it is again possible
  49.  *                                  to do a lexswitch() (dumb!).
  50.  *          14-Apr-83 Bob Denny    VAX-11 C workarounds.
  51.  *                                 Fix definition of toupper().
  52.  *            20-Nov-83 Scott Guthery  Adapt for IBM PC & DeSmet C
  53.  */
  54.  
  55. #ifdef  DOCUMENTATION
  56.  
  57. title   lex     A Lexical Analyser Generator
  58. index           A Lexical Analyser Generator
  59.  
  60. synopsis
  61.  
  62.         lex [-options] [-i grammar] [-o outfile] [-t table]
  63.  
  64. description
  65.  
  66.         Lex compiles a lexical analyser from a grammar and description of
  67.         actions.  It is described more fully in lex.doc: only usage is
  68.         described.  The following options are available:
  69.         .lm +16
  70.         .s.i-16;-a              Disable recognition of non-ASCII characters
  71.         (codes > 177 octal) for exception character classes (form [^ ...]).
  72.         .s.i-16;-d              Enable debugging code within lex.  Normally
  73.         needed only for debugging lex.
  74.         .s.i-16;-e              "Easy" command line. Saying "lex#-e#name" is the
  75.         same as saying:
  76.         .s.i 4;"lex -i name.lxi -o name.c -t name"
  77.         .s
  78.         Do not include devices or an extension on "name" or make it longer
  79.         than 8 characters, or you'll get several error messages.
  80.         .s.i-16;-i file         Read the grammar from the file.  If "-i" is not
  81.         specified, input will be read from the standard input.
  82.         .s.i-16;-m              Enable state minimization. Currently not
  83.  
  84.         implemented, switch is a no-op.
  85.         .s.i-16;-o file         Write the output to the file.  If "-o" is not
  86.         specified, output will be written to file "lextab.c".
  87.         .s.i-16;-s              "Stand-alone" switch.  Supresses the line
  88.         "#include <stdio.h>" normally generated in the lex output.  Use this
  89.         if LEX is generating a module to be used in a program which does not
  90.         use the "standard I/O" package.
  91.         .s.i-16;-t table        Name the recognizer "table" instead of the
  92.         default "lextab".  If -o is not given, output will be written to file
  93.         "table.c".
  94.         .s.i-16;-v [file]       Verify -- write internal tables to the
  95.         indicated file.  If "-v" is given without a file name argument,
  96.         tables will be written to "lex.out".
  97.         .lm -16
  98.  
  99. diagnostics
  100.  
  101.         The following error messages may occur on invocation.  See lex
  102.         documentation for information on compilation errors.
  103.         .lm +8
  104.         .s.i -8;Can't create ...
  105.         .s.i -8;Cannot open ...
  106.         .s.i -8;Illegal option.
  107.         .s.i -8;Illegal switch combination.
  108.         .s
  109.         "-i", "-o" or "-t" given with "-e" or vice-versa
  110.         .s.i -8;Table name too long.
  111.         .s
  112.         The table name (argument to "-t") must not be longer than 8 bytes.
  113.         .s.i -8;Missing table name.
  114.         .s.i -8;Missing input file.
  115.         .s.i -8;Missing output file.
  116.         .s.i -8;Missing name.
  117.         .lm -8
  118.  
  119. author
  120.         Charles Forsyth
  121.         Modified by Martin Minnow, Bob Denny & Scott Guthery
  122.  
  123. bugs
  124.  
  125. #endif
  126.  
  127. #include <stdio.h>
  128. #include "system.h"        /* includes system configuration constants */
  129.  
  130. extern char *lalloc();
  131. extern char tolower();
  132.  
  133. struct  nfa     nfa[MAXNFA];
  134. struct  nfa     *nfap = &nfa[1];
  135.  
  136. struct  xset    sets[NCHARS];
  137. char    insets[NCHARS];
  138.  
  139. struct  trans   trans[NTRANS];
  140. struct  trans   *transp = &trans[0];
  141.  
  142. char    ccls[NCCLS][(NCHARS+1)/NBPC];
  143. int     nccls;
  144.  
  145. int     ndfa;
  146. struct  dfa     dfa[MAXDFA];
  147. struct  move    move[NNEXT];
  148.  
  149. char    *tabname = "lextab";
  150. char    tabfile[15];
  151. char    *infile         = NULL;
  152. char    *outfile        = NULL;
  153.  
  154. #ifdef DEBUG
  155. char    *dumpfile       = "lex.out";
  156. int     lldebug = 0;
  157. #endif
  158.  
  159. int  llnxtmax = 0;
  160.  
  161. FILE llout;
  162. FILE lexin;
  163. FILE lexlog;
  164.  
  165. /*
  166.  * Flags.  Allow globals only for those requiring same. Some only
  167.  * used for checking for bad combos.
  168.  */
  169.         int     aflag = 0;      /* Ignore non-ASCII in [^ ...] */
  170. static  int     eflag = 0;      /* Easy command line */
  171. static  int     iflag = 0;      /* "-i" given */
  172.         int     mflag = 0;      /* Enable state minimization (not imp.) */
  173. static  int     oflag = 0;      /* "-o" given */
  174.         int     sflag = 0;      /* Supress "#include <stdio.h>" in output */
  175. static  int     tflag = 0;      /* "-t" given */
  176.  
  177. struct  set     *setlist = 0;
  178.  
  179. main(argc, argv)
  180. int argc;
  181. char *argv[];
  182. {
  183.         register char *cp, *cp2;
  184.  
  185. #ifdef DEBUG
  186.         int vflag;
  187.         vflag = 0;
  188. #endif
  189.  
  190.         for (; argc>1 && *argv[1]=='-'; argv++, argc--)
  191.         switch (tolower(argv[1][1])) {
  192.  
  193. #ifdef DEBUG
  194.         /*
  195.          * Create "verification" file, describing the scanner.
  196.          */
  197.         case 'v':                               /* -v => lex.out        */
  198.                 vflag++;                        /* -v x.out => x.out    */
  199.                 if (argc > 2 && argv[2][1] != '1') {
  200.                         --argc;
  201.                         dumpfile = (++argv)[1];
  202.                 }
  203.                 break;
  204.         /*
  205.          * Enable debug displays
  206.          */
  207.         case 'd':
  208.                 lldebug++;
  209.                 break;
  210. #endif
  211.         /*
  212.          * Enable state minimization. Currently not implemented.
  213.          */
  214.         case 'm':
  215.                 mflag++;
  216.                 break;
  217.  
  218.         /*
  219.          * Disable matching of non-ASCII characters (codes > 177(8))
  220.          * for exception character classes (form "[^ ...]").
  221.          */
  222.         case 'a':
  223.                 aflag++;
  224.                 break;
  225.  
  226.         /*
  227.          * Supress "#include <stdio.h>" in generated
  228.          * code for programs not using standard I/O.
  229.          */
  230.         case 's':
  231.                 sflag++;
  232.                 break;
  233.  
  234.         /*
  235.          * "Easy" command line
  236.          */
  237.         case 'e':
  238.                 if(iflag || oflag || tflag) {
  239.                         error("Illegal switch combination\n");
  240.                         exit(1);
  241.                 }
  242.                 if (--argc <= 1) {
  243.                         error("Missing name\n");
  244.                         exit(1);
  245.                 }
  246.                 if (strlen(tabname = (++argv)[1]) > 8) {
  247.                         error("Name too long\n");
  248.                         exit(1);
  249.                 }
  250.                 infile = malloc(14);
  251.                 outfile = malloc(12);
  252.                 strcpy(infile, tabname); strcat(infile, ".lxi");
  253.                 printf("Input read from %s\n", infile);
  254.                 if ((lexin = fopen(infile, "r")) == NULL) {
  255.                         error("Cannot open input \"%s\"\n", infile);
  256.                         exit(1);
  257.                 }
  258.                 strcpy(outfile, tabname); strcat(outfile, ".c");
  259.                 break;
  260.  
  261.         /*
  262.          * Specify input file name.
  263.          */
  264.         case 'i':
  265.                 if (eflag) {
  266.  
  267.                         error("Illegal switch combination\n");
  268.                         exit(1);
  269.                 }
  270.                 iflag++;
  271.                 if (--argc <= 1) {
  272.                         error("Missing input file\n");
  273.                         exit(1);
  274.                 }
  275.                 infile = (++argv)[1];
  276.                 printf("Input read from %s\n", infile);
  277.                 if ((lexin = fopen(infile, "r")) == NULL) {
  278.                         error("Cannot open input \"%s\"\n", infile);
  279.                         exit(1);
  280.                 }
  281.                 break;
  282.  
  283.         /*
  284.          * Specify output file name. Default = "lextab.c"
  285.          */
  286.         case 'o':
  287.                 if (eflag) {
  288.                         error("Illegal switch combination\n");
  289.                         exit(1);
  290.                 }
  291.                 oflag++;
  292.                 if (--argc <= 1) {
  293.                         error("Missing output file");
  294.                         exit(1);
  295.                 }
  296.                 outfile = (++argv)[1];
  297.                 break;
  298.  
  299.         /*
  300.          * Specify table name.  Default = "lextab.c".  If "-o"
  301.          * not given, output will go to "tabname.c".
  302.          */
  303.         case 't':
  304.                 if (eflag) {
  305.                         error("Illegal switch combination\n");
  306.                         exit(1);
  307.                 }
  308.                 tflag++;
  309.                 if (--argc <= 1) {
  310.                         error("Missing table name");
  311.                         exit(1);
  312.                 }
  313.                 if (strlen(tabname = (++argv)[1]) > 8) {
  314.                         error("Table name too long\n");
  315.                         exit(1);
  316.                 }
  317.                 break;
  318.  
  319.         default:
  320.                 error("Illegal option: %s\n", argv[1]);
  321.                 exit(1);
  322.         }
  323.  
  324. #ifdef DEBUG
  325.  
  326.         cp = (vflag) ? dumpfile : "NUL";
  327.         printf("Log written to %s\n", cp);
  328.         if ((lexlog = fopen(cp, "w")) == NULL) {
  329.                 error("Cannot open \"%s\"", cp);
  330.                 exit(1);
  331.  
  332.         }
  333. #endif
  334.         if (infile == NULL) {
  335.                 infile = malloc(31);
  336.                 strcpy(infile, "lex.lxi");
  337.         }
  338.         cp = infile;                    /* Fold infile to lower case */
  339. /*
  340.  * The following 2 loops cannot use the form "*cp++ = tolower(*cp)" 
  341.  * due to a bug in VAX-11 C V1.0-09 where the pointer increment
  342.  * is done too soon (!).
  343.  */
  344.         while(*cp)
  345.                 {
  346.                 *cp = tolower(*cp);
  347.                 cp++;
  348.                 }
  349.         cp = tabname;                   /* Fold tabname to lower case */
  350.         while(*cp)
  351.                 {
  352.                 *cp = tolower(*cp);
  353.                 cp++;
  354.                 }
  355.         if (outfile == NULL) {
  356.                 /*
  357.                  * Typical hacker's idiom!
  358.                  */
  359.                 for (cp = tabname, cp2 = tabfile; *cp2 = *cp++;)
  360.                         cp2++;
  361.                 for (cp = ".c"; *cp2++ = *cp++;)
  362.                         ;
  363.                 outfile = tabfile;
  364.         }
  365.         printf("Analyzer written to %s\n", outfile);
  366.         if ((llout = fopen(outfile, "w"))==NULL) {
  367.                 error("Can't create %s\n", outfile);
  368.                 exit(1);
  369.         }
  370.  
  371.         heading();
  372.         fprintf(stderr, "Parse LEX source ...\n");
  373.         if (yyparse())
  374.                 error("Parse failed\n");
  375.         fprintf(stderr, "Build NFA then DFA ...\n");
  376.         dfabuild();                                             /* 01+ */
  377.         fprintf(stderr, "Minimize DFA ...\n");
  378.         dfamin();
  379.         fprintf(stderr, "Create C source ...\n");
  380.         dfaprint();
  381.         dfawrite();
  382. #ifdef DEBUG
  383.         stats();
  384.         fclose(lexlog);
  385. #endif                                                          /* 01- */
  386.         fprintf(stderr, "\07LEX done.\n");
  387.  
  388.         fclose(llout);
  389. } /** END OF MAIN **/
  390.  
  391. /*
  392.  * This module was moved here from out.c so it could be called from
  393.  * ytab.c residing in same overlay region as out.c.
  394.  * 02-Dec-80  Bob Denny.
  395.  */
  396.                                                                 /* 01+ */
  397. ending()
  398. {
  399.         static int ended;
  400.  
  401.         if (ended++)
  402.                 return;
  403.         fprintf(llout, "\t}\n\treturn(LEXSKIP);\n}\n");
  404.         setline();
  405. }
  406.  
  407. #ifdef DEBUG
  408. stats()
  409. {
  410.         fprintf(lexlog, "\n");
  411.         fprintf(lexlog, "%d/%d NFA states, %d/%d DFA states\n",
  412.                 nfap-nfa, MAXNFA, ndfa, MAXDFA);
  413.         fprintf(lexlog, "%d/%d entries in move vectors\n", llnxtmax, NNEXT);
  414. }
  415.  
  416. /*
  417.  * Print a state set on { ... } form on lexlog.
  418.  */
  419. pset(t, nf)
  420. register struct set *t;
  421. {
  422.         register i;
  423.  
  424.         fprintf(lexlog, "{");
  425.         for (i = 0; i < t->s_len; i++)
  426.                 if (nf)
  427.                         fprintf(lexlog, " %d", t->s_els[i]-nfa); else
  428.                         fprintf(lexlog, " %d", t->s_els[i]);
  429.         fprintf(lexlog, "}");
  430. }
  431.  
  432. /*
  433.  * Print a character to lexlog in readable form.
  434.  * Returns the number of characters generated.
  435.  */
  436. chprint(ch)
  437. {
  438.         register char *s;
  439.  
  440.         ch &= 0377;
  441.         switch (ch) {
  442.         case '\t':
  443.                 s = "\\t";
  444.                 break;
  445.         case '\n':
  446.                 s = "\\n";
  447.                 break;
  448.         case '\b':
  449.                 s = "\\b";
  450.  
  451.                 break;
  452.         case '\r':
  453.                 s = "\\r";
  454.                 break;
  455.         default:
  456.                 if(ch<040 || ch>=0177)
  457.                         {
  458.                         fprintf(lexlog, "\\%03o", ch);
  459.                         return(4);
  460.                         }
  461.                 else
  462.                         {
  463.                         putc(ch, lexlog);
  464.                         return(1);
  465.                         }
  466.         }
  467.         fprintf(lexlog, s);
  468.         return(2);
  469. }
  470. #endif
  471.  
  472. /*
  473.  * The following functions simply
  474.  * allocate various kinds of
  475.  * structures.
  476.  */
  477. struct nfa *
  478. newnfa(ch, nf1, nf2)
  479. struct nfa *nf1, *nf2;
  480. {
  481.         register struct nfa *nf;
  482.  
  483.         if ((nf = nfap++) >= &nfa[MAXNFA]) {
  484.                 error("Too many NFA states");
  485.                 exit(1);
  486.         }
  487.         nf->n_char = ch;
  488.         nf->n_succ[0] = nf1;
  489.         nf->n_succ[1] = nf2;
  490.         nf->n_trans = 0;
  491.         nf->n_flag = 0;
  492.         nf->n_look = 0;
  493.         return(nf);
  494. }
  495.  
  496. newdfa()
  497. {
  498.         register struct dfa *df;
  499.  
  500.         if ((df = &dfa[ndfa++]) >= &dfa[MAXDFA]) {
  501.                 error("Out of dfa states");
  502.                 exit(1);
  503.         }
  504.         return(df);
  505. }
  506.  
  507. char *
  508. newccl(ccl)
  509. char *ccl;
  510. {
  511.         register char *p, *q;
  512.         register i;
  513.  
  514.         int j;
  515.  
  516.         for (j = 0; j < nccls; j++) {
  517.                 p = ccl;
  518.                 q = ccls[j];
  519.                 for (i = sizeof(ccls[j]); i--;)
  520.                         if (*p++ != *q++)
  521.                                 goto cont;
  522.                 return(ccls[j]);
  523.         cont:;
  524.         }
  525.         if (nccls >= NCCLS) {
  526.                 error("Too many character classes");
  527.                 exit(1);
  528.         }
  529.         p = ccl;
  530.         q = ccls[j = nccls++];
  531.         for (i = sizeof(ccls[j]); i--;)
  532.                 *q++ = *p++;
  533.         return(ccls[j]);
  534. }
  535.  
  536. struct trans *
  537. newtrans(st, en)
  538. struct nfa *st, *en;
  539. {
  540.         register struct trans *tp;
  541.  
  542.         if ((tp = transp++) >= &trans[NTRANS]) {
  543.                 error("Too many translations");
  544.                 exit(1);
  545.         }
  546.         tp->t_start = st;
  547.         tp->t_final = en;
  548.         en->n_trans = tp;
  549.         return(tp);
  550. }
  551.  
  552. /*
  553.  * Create a new set. `sf', if set, indicates that the elements of the
  554.  * set are states of an NFA). If `sf' is not set, the elements are state
  555.  * numbers of a DFA.
  556.  */
  557. struct set *
  558. newset(v, i, sf)
  559. register struct nfa **v;
  560. register i;
  561. {
  562.         register struct set *t;
  563.         register k;
  564.         int setcomp();
  565.  
  566.         qsort(v, i, sizeof(*v), setcomp);
  567.         for (t = setlist; t; t = t->s_next)
  568.                 if (t->s_len==i && eqvec(t->s_els, v, i))
  569.                         return(t);
  570.         t = lalloc(1, sizeof(*t)+i*sizeof(t->s_els[0]), "set nodes");
  571.         t->s_next = setlist;
  572.  
  573.         setlist = t;
  574.         t->s_final = 0;
  575.         t->s_state =  0;
  576.         t->s_flag = 0;
  577.         t->s_len = i;
  578.         t->s_group = 0;
  579.         t->s_look = 0;
  580.         for (v += i; i;) {
  581.                 --v;
  582.                 if (sf) {
  583.                         if ((*v)->n_char==FIN)
  584.                                 t->s_final =  (*v)-nfa;
  585.                         if ((*v)->n_flag&LOOK)
  586.                                 t->s_look |= 1<<(*v)->n_look;
  587.                 } else {
  588.                         k = *v;
  589.                         dfa[k].df_name->s_group = t;
  590.                 }
  591.                 t->s_els[--i] = *v;
  592.         }
  593.         return(t);
  594. }
  595.  
  596. setcomp(n1p, n2p)
  597. struct nfa **n1p, **n2p;
  598. {
  599.         register struct nfa *n1, *n2;
  600.  
  601.         n1 = *n1p;
  602.         n2 = *n2p;
  603.         if (n1 > n2)
  604.                 return(1);
  605.         if (n1==n2)
  606.                 return(0);
  607.         return(-1);
  608. }
  609.  
  610. eqvec(a, b, i)
  611. register *a, *b, i;
  612. {
  613.         if (i)
  614.                 do {
  615.                         if (*a++ != *b++)
  616.                                 return(0);
  617.                 } while (--i);
  618.         return(1);
  619. }
  620.  
  621. /*
  622.  * Ask for core, and complain if there is no more.
  623.  */
  624. char *
  625. lalloc(n, s, w)
  626. char *w;
  627. {
  628.         register char *cp;
  629.  
  630.         if ((cp = calloc(n, s)) == NULL) {
  631.                 fprintf(stderr, "No space for %s", w);
  632. #ifdef DEBUG
  633.                 if (lldebug)
  634.  
  635.                         dfaprint();
  636. #endif
  637.                 exit(1);
  638.         }
  639.         return(cp);
  640. }
  641.  
  642. error(format, argument)
  643. char *format, *argument;
  644. {
  645.     fprintf(stderr, format, argument);
  646. }
  647.